package linkedlist;

class Node{
    //表示每个节点存储的值
    String value;
    //表示下一个节点
    Node next;
    public Node(String value){
        this.value = value;
        this.next = null;
    }
}
public class MyLinkedList {
    //head 指向头节点
    Node head = null;


    //头插
    public void addFirst(String value){
        //创建新节点
        Node newNode = new Node(value);
        //插入操作
        //1.先将插入的节点的 next 指向 head 指向的节点
        newNode.next = head;
        //再将 head 指向新节点
        head = newNode;
    }
    public void addLast(String value){
        //如果head 为 null 就直接插入
        if (head == null){
            addFirst(value);
            return;
        }
        //先找到链表的尾巴
        Node tail = head;
        while (tail.next != null){
            tail = tail.next;
        }
        //此时tail就指向了链表的最后一个元素

        //插入操作
        Node newNode = new Node(value);
        tail.next = newNode;
        newNode.next = null;
    }

    //指定位置插入
    public void add(int index, String value){
        //判断合法性
        if (index < 0 || index > size()){
            throw new RuntimeException("下标超出异常");
        }
        if (index == 0){
            addFirst(value);
            return;
        }
        //找到下标 index 的前一个节点
        Node prve = head;
        for (int i = 0; i < index - 1; i++){
            prve = prve.next;
        }
        //此时 prev 就指向 index 的前一个节点
        Node newNode = new Node(value);
        newNode.next = prve.next;
        prve.next = newNode;
    }

    //删除指定下标的元素
    public void remove(int index){
        //判断合法性
        if (index < 0 || index >= size()){
            throw new RuntimeException("下标超出异常");
        }
        if (index == 0){
            head = head.next;
            return;
        }
        //找到 index 的前一个节点
        Node prve = head;
        for (int i = 0; i < index - 1; i++){
            prve = prve.next;
        }
        //此时 prve 就指向被删除元素的前一个节点
        Node toRemove = prve.next;
        prve.next = toRemove.next;
    }

    //判断某个数值是否存在
    public boolean contain(String value){
        //遍历链表
        for(Node cur = head; cur != null; cur = cur.next){
            if (cur.value.equals(value)){
                return true;
            }
        }
        return false;
    }
    public int indexOf(String value){
        int index = 0;
        for (Node cur = head; cur != null; cur = cur.next){
            if (cur.value.equals(value)){
                return index;
            }
            index++;
        }
        return -1;
    }


    //链表的长度
    public int size(){
        int size = 0;
        for (Node cur = head; cur != null; cur = cur.next){
            size++;
        }
        return size;
    }
    public String toString(){
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append(("["));
        //遍历链表
        //使用 cur 引用来指向每一个节点
        for (Node cur = head; cur != null; cur = cur.next){
            stringBuilder.append(cur.value);
            if (cur.next != null){
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("]");
        return stringBuilder.toString();
    }
}